The present invention relates to scaling (i.e., enlarging or reducing) color images. It finds particular application in conjunction with choosing an appropriate algorithm for scaling an antialiased original color image before it is combined with a new image, and will be described with particular reference thereto. It will be appreciated, however, that the invention will also find application for choosing a scaling algorithm for video images or other types of images.
The use of graphics in computer and communication applications is very widespread and is becoming increasingly more prevalent. A computing device often transmits a document including graphical data to a printing device using a page description language. Page description languages (e.g., the PostScript(copyright) language) include interpretive programming commands useful for implementing powerful graphics capabilities. When transmitted via a page description language, graphical data is typically first converted to a bit-map data file. Printing devices then include an interpreter for deciphering the bit-map data into raster graphics.
Recently, page description interpreters have begun to include means for antialiased images to be printed. In the context of gray-scale or black and white bit-map data, antialiasing refers to introducing intermediate intensity levels along edges of the object for smoothing jagged lines in lower resolution images. Similarly, in the context of color bit-map data, antialiasing refers to introducing a single color which is representative of various colors along the edges of an object to achieve the same effect in lower resolution color images.
Devices such as scanners and/or CCD cameras produce data which are similar to antialiased data. Data produced by those devices often includes optical blurring in intermediate values appearing along edges. The optical blurring provides the appearance of smoothness.
Because an antialiased image by definition is a gray-scale image, it is not possible to print an antialiased image directly on a black and white printer (i.e., a printer not capable of producing gray-scale images). Therefore, antialiased gray-scale images must first be converted to black and white (binary) images before they are printed to such printers. Typically, converting an antialiased image to a black and white image includes xe2x80x9cscaling-upxe2x80x9d the image.
One benefit of using antialiasing is that it reduces the total amount of data that must be computed and transmitted. As an example, assume a computer creates a 300 dot per inch (xe2x80x9cdpixe2x80x9d) by 300 dpi antialiased gray-scale image. The computer transmits the 300 dpixc3x97300 dpi gray-scale image to a black and white printer (e.g., via a cable). The printer includes a scaling algorithm which scales-up the 300 dpixc3x97300 dpi gray-scale image to a 1200 dpixc3x971200 dpi image and subsequently converts it to black and white. Because the resulting 1200 dpixc3x971200 dpi image is black and white, it only has a single bit of data per pixel. The 300 dpixc3x97300 dpi gray-scale image, on the other hand, has multiple (e.g., eight (8)) bits of data per pixel (i.e., one level of pixel data for each shade of gray). For each level of the 300 dpixc3x97300 dpi gray-scale image, the 1200 dpixc3x971200 dpi black and white image has four (4) times as many pixels in each of the four (4) directions. In this sense, the 1200 dpixc3x971200 dpi black and white image appears to contain sixteen (16) times as much data. However., because the 1200 dpixc3x971200 dpi black and white image only contains one (1) bit per pixel and the 300 dpixc3x97300 dpi gray-scale image contains eight (8) bits per pixel, the 1200 dpixc3x971200 dpi scaled-up image actually only contains two (2) times as much data.
In general, the cost of computing power necessary for manipulating data is at least proportional to the amount of data to be manipulated. Therefore, it is cheaper to manipulate data for lower resolution images. In the example described above, the lower resolution gray-scale image is stored and manipulated until the image is printed. Only at that time is the gray-scale image scaled-up to the black and white image. Consequently, a high resolution black and white image is produced using only about one-half of the computing power which would typically be required to achieve such an image. Similarly, that image may be transmitted using only one-half of the transmission bandwidth.
In addition to printing, there are other reasons for wanting to scale up an image, or some portion thereof. For example, it is often desirable to combine new image data with an existing image. Combining the images results in different pixel values for the final image. In this case, both images can be either gray-scale or color. Sharper images are produced when higher-resolution, as opposed to lower-resolution, images are combined. Therefore, it is desirable to scale-up an original antialiased image before it is combined with a second image.
One method of combining images is known as alpha-blending. For color images, alpha-blending uses the fractional coverage of the object contained in the new image to determine the fraction of the new color to be combined with the existing background (i.e., the original color). Alpha-blending assumes the background is a constant color. Specifically,:
INEW=IBACKGROUND+xcex1(IOBJECTxe2x88x92IBACKGROUND)
where xcex1 is the fraction of the pixel covered by the new object. While alpha-blending works for zero or full coverage, it is not reliable when a background object only partially covers a pixel.
FIGS. 1A, 1B and 1C illustrate three different high-resolution pixels representing edge geometries of a pixel in an original color image. Note that in FIGS. 1A, 1B and 1C only one-half of the original image covers the pixel. More specifically, one-half of the original pixel is solid cyan 2 while the other half of the pixel is solid white 3. FIG. 2 shows an image of the pixel after any one of the high-resolution pixels of FIGS. 1A, 1B, and 1C is antialiased. The antialiased pixel shown in FIG. 2 is represented by a shade 4 of cyan which is lighter than the original pixels shown in FIGS. 1A, 1B and 1C. As discussed above, one drawback of the weighted average technique of alpha-blending is that the geometry of the original image is lost when an image is antialiased. In other words, color distinctions along edges of the original image are lost. Therefore, if the antialiased original image is combined with a second image, correct colors may not be produced along edges of the resulting image.
FIGS. 3A, 3B and 3C illustrate the three high-resolution pixel geometries of FIGS. 1A, 1B and 1C, respectively, in which a new object having a solid magenta color 5 covering the right-half of the pixel is to be combined with the original cyan object. FIGS. 4A, 4B and 4C illustrate the correct rasterization which would result from alpha-blending the images of FIGS. 3A, 3B and 3C, respectively. More specifically, FIG. 3A illustrates a geometry having a left-half which is cyan 2 and a right-half which is magenta 5 (i.e., the new magenta 5 object does not cover any of the original cyan 2 object). FIG. 4A shows a dark purple pixel 6 results when the colors of FIG. 3A are blended correctly. FIG. 3B illustrates a geometry having a left-half which is white 3 and a right-half which is magenta 5 (i.e., the new magenta 5 object completely covers the original cyan object). FIG. 4B shows a pink pixel 7 results when the colors of FIG. 3B are blended correctly. FIG. 3C illustrates a geometry having a top left-half which is white 3, a bottom left-half which is cyan 2, and a right-half which is magenta 5 (i.e., the new magenta 5 object covers one-half {fraction (1/2)} of the original cyan 2 object). FIG. 4C shows a light purple pixel 8 results when the colors of FIG. 3C are blended correctly.
As discussed above, because there is only a limited amount of memory on a computer, the high-resolution geometry of the original pixel (FIGS. 1A, 1B and 1C) is typically purged from memory once the original image is antialiased. Therefore, only the antialiased pixel (FIG. 2) is available to provide the geometry of the original object. Consequently, when it becomes desirable to combine the original object with a new object, it has been necessary in the past to assume an average case for which one of the three edge geometries shown in FIGS. 1A, 1B, and 1C accurately describe the geometry of the original object. As FIGS. 4A, 4B and 4C show, very different results are obtained for the final pixel depending upon which one of the three original geometries is chosen. Therefore, a noticeably incorrect result is produced for the final pixel when the average case is wrong as to the geometry of the edge pixel in the original image.
The present invention provides a new and improved apparatus and method which overcomes the above-referenced problems and others.
A method for computing color information of a scaled version of a pixel of interest includes identifying pixel color values for pixels in a neighborhood including the pixel of interest. The pixels in the neighborhood form a pattern. The pixel color values of the pixel of interest and the plurality of neighboring pixels are transformed to produce a plurality of transformed values. A geometric pattern, which resembles the pattern formed by the pixels in the neighborhood, is identified as a function of the transformed values. An appropriate scaling algorithm for scaling the geometric pattern is selected. The scaled version of the pixel of interest, along with the color information for the scaled pixel, is produced by applying the selected scaling algorithm to the pixel of interest.
In accordance with one aspect of the invention, a plurality of scaling algorithm identifiers are stored in a hash-table. The selecting step includes retrieving one of the scaling algorithm identifiers from the hash-table.
In accordance with a more limited aspect of the invention, as part of retrieving one of the scaling algorithm identifiers, an address is calculated where the identifier of the scaling algorithm is stored within the hash-table.
In accordance with a more limited aspect of the invention, the address is calculated as a modulus of a size of the hash-table and a multiple of a concatenation of at least one bit from the transformed values.
In accordance with another aspect of the invention, one of twelve geometric patterns are identified from a group including a flat geometric pattern, a northwest stroke geometric pattern, a northeast stroke geometric pattern, a vertical stroke geometric pattern, a horizontal stroke geometric pattern, a northwest edge geometric pattern, a northeast edge geometric pattern, a vertical edge geometric pattern, a horizontal edge geometric pattern, a corner geometric pattern, a cross geometric pattern, and an unknown geometric pattern.
One advantage of the present invention is that an appropriate algorithm is selected for scaling-up an image which has previously been antialiased.
Another advantage of the present invention is that when the scaled-up image is combined with a second image, correct rasterization is achieved along overlapping geometries such as edges, strokes, crosses, etc.
Still further advantages of the present invention will become apparent to those of ordinary skill in the art upon reading and understanding the following detailed description of the preferred embodiments.